package lt397
/*
397. 整数替换
给定一个正整数 n ，你可以做如下操作：
	如果 n 是偶数，则用 n / 2替换 n 。
	如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
n 变为 1 所需的最小替换次数是多少？
*/
/*
若n是2的幂，则return 幂
将n变为2的幂，然后返回幂 总是最快的吧
观察+1 -1的规律。除了3 7 ，+1变为4的倍数的奇数，适合+1
如何判断某个数字+1是4的倍数： 通过二进制
	二进制奇数，最右位是1  若右二是1，则+1后右边出现两个0
*/
func integerReplacement(n int) int {
	res := 0
	for n>1 {
		if n&1 == 0{ //偶数  最后一位为0
			n >>= 1  //移位  ÷2
		}else if (n+1)%4==0 && n!=3 {//末尾二位为11
			n++ //+1
		}else{  //末尾两位是01  奇数最后一位肯定是1
			n--
		}
		res ++
	}
	return res
}